package com.agile.leetcode.hot.easy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 696. 计数二进制子串
 * 给定一个字符串 s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。
 * <p>
 * 重复出现的子串要计算它们出现的次数。
 * <p>
 * <p>
 * <p>
 * 示例 1 :
 * <p>
 * 输入: "00110011"
 * 输出: 6
 * 解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
 * <p>
 * 请注意，一些重复出现的子串要计算它们出现的次数。
 * <p>
 * 另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
 * 示例 2 :
 * <p>
 * 输入: "10101"
 * 输出: 4
 * 解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
 * <p>
 * <p>
 * 提示：
 * <p>
 * s.length 在1到50,000之间。
 * s 只包含“0”或“1”字符。
 *
 * @Author:ChenZhangKun
 * @Date: 2021/6/3 9:26
 */
public class CountBinarySubstrings {
    public static void main(String[] args) {
        String s = "00110011";
        CountBinarySubstrings c = new CountBinarySubstrings();
        System.out.println(c.countBinarySubstrings_1(s));
    }

    /**
     * 暴力解法
     *
     * @param s
     * @return
     */
    public int countBinarySubstrings(String s) {
        // 拿到长度
        int length = s.length();
        //
        if (length == 0 || length == 1) {
            return 0;
        }
        int count = 0;
        // 遍历
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length + 1; j++) {
                // 拿到子串
                String tempStr = s.substring(i, j);
                boolean b = isSuteableStr(tempStr);
                if (b) {
                    count++;
                    System.out.println(tempStr);
                }
            }
        }
        return count;
    }

    private boolean isSuteableStr(String tempStr) {

        // 判断是否连续
        char[] chars = tempStr.toCharArray();
        if (chars.length % 2 == 1) {
            // 奇数
            return false;
        }
        char[] c = Arrays.copyOf(chars, chars.length);
        // 排序，自然生序
        Arrays.sort(c);
        // 不相等说明不连续
        boolean b = new String(c).equals(tempStr);
        if (!b) {
            // 降序排序
            char temp;
            for (int i = 0; i < c.length / 2; i++) {
                temp = c[i];
                c[i] = c[c.length - i - 1];
                c[c.length - i - 1] = temp;
            }
            if (!new String(c).equals(tempStr)) {
                return false;
            }
        }
        // 判断0 1 的个数是否相等
        List<Character> list = new ArrayList<>(10);
        for (char achar : chars) {
            if (achar == '1') {
                list.add(achar);
            }
        }
        if (list.size() == chars.length / 2) {
            return true;
        }
        return false;
    }

    /**
     * 官方思路
     * 先统计连续的0和1分别有多少个，如：111100011000，得到4323；在4323中的任意相邻两个数字，取小的一个加起来，就是3+2+2 = 7.
     *
     * @param s
     * @return
     */
    public int countBinarySubstrings_1(String s) {
        // 拿到长度
        int length = s.length();
        //
        if (length == 0 || length == 1) {
            return 0;
        }
        // 计算数字个数
        int index = 0;
        // 统计个数
        int count = 0;
        // 临时数字
        char temp = ' ';
        // 总合
        int result = 0;
        List<Integer> list = new ArrayList<>();
        while (index < length) {
            // 第一个的时候
            if (index == 0) {
                temp = s.charAt(index);
                count++;
            } else {
                // 对比
                char c = s.charAt(index);
                if (c != temp) {
                    // 加入集合
                    list.add(count);
                    // 归1
                    count = 1;
                    // temp重置
                    temp = c;
                } else {
                    count++;
                }
            }
            index++;
        }
        //  最后剩余的需要计入集合
        list.add(count);
        int tempMin = 0;
        for (int i = 0; i < list.size() - 1; i++) {
            int n = i + 1;
            tempMin = Math.min(list.get(i), list.get(n));
            result += tempMin;
        }
        return result;
    }
}
